#ifndef _LINUX_LK_LIST_H
#define _LINUX_LK_LIST_H

/*
#include <linux/types.h>
#include <linux/stddef.h>
#include <linux/poison.h>
#include <linux/const.h>
#include <linux/kernel.h>
*/
#include <stdio.h>

/*
 * Simple doubly linked lk_list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lk_lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */

struct lk_list_head {
	struct lk_list_head *next, *prev;
};

#define WRITE_ONCE(_var_,_val_)		(_var_) = (_val_)
#define READ_ONCE(_var_)		(_var_)

#define POISON_POINTER_DELTA 0
#define LK_LIST_POISON1  ((struct lk_list_head *) 0x100 + POISON_POINTER_DELTA)
#define LK_LIST_POISON2  ((struct lk_list_head *) 0x200 + POISON_POINTER_DELTA)

#define LK_LIST_HEAD_INIT(name) { &(name), &(name) }

#define LK_LIST_HEAD(name) \
	struct lk_list_head name = LK_LIST_HEAD_INIT(name)

void INIT_LK_LIST_HEAD(struct lk_list_head *lk_list);
void lk_list_add(struct lk_list_head *_new, struct lk_list_head *head);
void lk_list_add_tail(struct lk_list_head *_new, struct lk_list_head *head);
void lk_list_del(struct lk_list_head *entry);
void lk_list_replace(struct lk_list_head *old, struct lk_list_head *_new);
void lk_list_replace_init(struct lk_list_head *old, struct lk_list_head *_new);
void lk_list_del_init(struct lk_list_head *entry);
void lk_list_move(struct lk_list_head *lk_list, struct lk_list_head *head);
void lk_list_move_tail(struct lk_list_head *lk_list, struct lk_list_head *head);
int lk_list_is_last(const struct lk_list_head *lk_list, const struct lk_list_head *head);
int lk_list_empty(const struct lk_list_head *head);
int lk_list_empty_careful(const struct lk_list_head *head);
void lk_list_rotate_left(struct lk_list_head *head);
int lk_list_is_singular(const struct lk_list_head *head);
void lk_list_cut_position(struct lk_list_head *lk_list, struct lk_list_head *head, struct lk_list_head *entry);
void lk_list_splice(const struct lk_list_head *lk_list, struct lk_list_head *head);
void lk_list_splice_tail(struct lk_list_head *lk_list, struct lk_list_head *head);
void lk_list_splice_init(struct lk_list_head *lk_list, struct lk_list_head *head);
void lk_list_splice_tail_init(struct lk_list_head *lk_list, struct lk_list_head *head);

/**
 * lk_list_entry - get the struct for this entry
 * @ptr:	the &struct lk_list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the lk_list_head within the struct.
 */
#define lk_list_entry(ptr, type, member) \
	container_of(ptr, type, member)

/**
 * lk_list_first_entry - get the first element from a lk_list
 * @ptr:	the lk_list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Note, that lk_list is expected to be not empty.
 */
#define lk_list_first_entry(ptr, type, member) \
	lk_list_entry((ptr)->next, type, member)

/**
 * lk_list_last_entry - get the last element from a lk_list
 * @ptr:	the lk_list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Note, that lk_list is expected to be not empty.
 */
#define lk_list_last_entry(ptr, type, member) \
	lk_list_entry((ptr)->prev, type, member)

/**
 * lk_list_first_entry_or_null - get the first element from a lk_list
 * @ptr:	the lk_list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Note that if the lk_list is empty, it returns NULL.
 */
#define lk_list_first_entry_or_null(ptr, type, member) \
	(!lk_list_empty(ptr) ? lk_list_first_entry(ptr, type, member) : NULL)

/**
 * lk_list_next_entry - get the next element in lk_list
 * @p_node:	the type * to cursor
 * @member:	the name of the lk_list_head within the struct.
 */
#define lk_list_next_entry(p_node, type, member) \
	lk_list_entry((p_node)->member.next, type, member)

/**
 * lk_list_prev_entry - get the prev element in lk_list
 * @p_node:	the type * to cursor
 * @member:	the name of the lk_list_head within the struct.
 */
#define lk_list_prev_entry(p_node, type, member) \
	lk_list_entry((p_node)->member.prev, type, member)

/**
 * lk_list_for_each	-	iterate over a lk_list
 * @p_node:	the &struct lk_list_head to use as a loop cursor.
 * @head:	the head for your lk_list.
 */
#define lk_list_for_each(p_node, head) \
	for (p_node = (head)->next; p_node != (head); p_node = p_node->next)

/**
 * lk_list_for_each_prev	-	iterate over a lk_list backwards
 * @p_node:	the &struct lk_list_head to use as a loop cursor.
 * @head:	the head for your lk_list.
 */
#define lk_list_for_each_prev(p_node, head) \
	for (p_node = (head)->prev; p_node != (head); p_node = p_node->prev)

/**
 * lk_list_for_each_safe - iterate over a lk_list safe against removal of lk_list entry
 * @p_node:	the &struct lk_list_head to use as a loop cursor.
 * @n:		another &struct lk_list_head to use as temporary storage
 * @head:	the head for your lk_list.
 */
#define lk_list_for_each_safe(p_node, n, head) \
	for (p_node = (head)->next, n = p_node->next; p_node != (head); \
		p_node = n, n = p_node->next)

/**
 * lk_list_for_each_prev_safe - iterate over a lk_list backwards safe against removal of lk_list entry
 * @p_node:	the &struct lk_list_head to use as a loop cursor.
 * @n:		another &struct lk_list_head to use as temporary storage
 * @head:	the head for your lk_list.
 */
#define lk_list_for_each_prev_safe(p_node, n, head) \
	for (p_node = (head)->prev, n = p_node->prev; \
	     p_node != (head); \
	     p_node = n, n = p_node->prev)

/**
 * lk_list_for_each_entry	-	iterate over lk_list of given type
 * @p_node:	the type * to use as a loop cursor.
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 */
#define lk_list_for_each_entry(p_node, head, type, member)				\
	for (p_node = lk_list_first_entry(head, type, member);	\
	     &p_node->member != (head);					\
	     p_node = lk_list_next_entry(p_node, type, member))

/**
 * lk_list_for_each_entry_reverse - iterate backwards over lk_list of given type.
 * @p_node:	the type * to use as a loop cursor.
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 */
#define lk_list_for_each_entry_reverse(p_node, head, member)			\
	for (p_node = lk_list_last_entry(head, typeof(*p_node), member);		\
	     &p_node->member != (head); 					\
	     p_node = lk_list_prev_entry(p_node, member))

/**
 * lk_list_prepare_entry - prepare a p_node entry for use in lk_list_for_each_entry_continue()
 * @p_node:	the type * to use as a start point
 * @head:	the head of the lk_list
 * @member:	the name of the lk_list_head within the struct.
 *
 * Prepares a p_node entry for use as a start point in lk_list_for_each_entry_continue().
 */
#define lk_list_prepare_entry(p_node, head, member) \
	((p_node) ? : lk_list_entry(head, typeof(*p_node), member))

/**
 * lk_list_for_each_entry_continue - continue iteration over lk_list of given type
 * @p_node:	the type * to use as a loop cursor.
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Continue to iterate over lk_list of given type, continuing after
 * the current position.
 */
#define lk_list_for_each_entry_continue(p_node, head, member) 		\
	for (p_node = lk_list_next_entry(p_node, member);			\
	     &p_node->member != (head);					\
	     p_node = lk_list_next_entry(p_node, member))

/**
 * lk_list_for_each_entry_continue_reverse - iterate backwards from the given point
 * @p_node:	the type * to use as a loop cursor.
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Start to iterate over lk_list of given type backwards, continuing after
 * the current position.
 */
#define lk_list_for_each_entry_continue_reverse(p_node, head, member)		\
	for (p_node = lk_list_prev_entry(p_node, member);			\
	     &p_node->member != (head);					\
	     p_node = lk_list_prev_entry(p_node, member))

/**
 * lk_list_for_each_entry_from - iterate over lk_list of given type from the current point
 * @p_node:	the type * to use as a loop cursor.
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Iterate over lk_list of given type, continuing from current position.
 */
#define lk_list_for_each_entry_from(p_node, head, member) 			\
	for (; &p_node->member != (head);					\
	     p_node = lk_list_next_entry(p_node, member))

/**
 * lk_list_for_each_entry_safe - iterate over lk_list of given type safe against removal of lk_list entry
 * @p_node:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 */
#define lk_list_for_each_entry_safe(p_node, n, head, type, member)			\
	for (p_node = lk_list_first_entry(head, type, member),	\
		n = lk_list_next_entry(p_node, type, member);			\
	     &p_node->member != (head); 					\
	     p_node = n, n = lk_list_next_entry(n, type, member))

/**
 * lk_list_for_each_entry_safe_continue - continue lk_list iteration safe against removal
 * @p_node:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Iterate over lk_list of given type, continuing after current point,
 * safe against removal of lk_list entry.
 */
#define lk_list_for_each_entry_safe_continue(p_node, n, head, member) 		\
	for (p_node = lk_list_next_entry(p_node, member), 				\
		n = lk_list_next_entry(p_node, member);				\
	     &p_node->member != (head);						\
	     p_node = n, n = lk_list_next_entry(n, member))

/**
 * lk_list_for_each_entry_safe_from - iterate over lk_list from current point safe against removal
 * @p_node:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Iterate over lk_list of given type from current point, safe against
 * removal of lk_list entry.
 */
#define lk_list_for_each_entry_safe_from(p_node, n, head, member) 			\
	for (n = lk_list_next_entry(p_node, member);					\
	     &p_node->member != (head);						\
	     p_node = n, n = lk_list_next_entry(n, member))

/**
 * lk_list_for_each_entry_safe_reverse - iterate backwards over lk_list safe against removal
 * @p_node:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_list_head within the struct.
 *
 * Iterate backwards over lk_list of given type, safe against removal
 * of lk_list entry.
 */
#define lk_list_for_each_entry_safe_reverse(p_node, n, head, member)		\
	for (p_node = lk_list_last_entry(head, typeof(*p_node), member),		\
		n = lk_list_prev_entry(p_node, member);			\
	     &p_node->member != (head); 					\
	     p_node = n, n = lk_list_prev_entry(n, member))

/**
 * lk_list_safe_reset_next - reset a stale lk_list_for_each_entry_safe loop
 * @p_node:	the loop cursor used in the lk_list_for_each_entry_safe loop
 * @n:		temporary storage used in lk_list_for_each_entry_safe
 * @member:	the name of the lk_list_head within the struct.
 *
 * lk_list_safe_reset_next is not safe to use in general if the lk_list may be
 * modified concurrently (eg. the lock is dropped in the loop body). An
 * exception to this is if the cursor element (p_node) is pinned in the lk_list,
 * and lk_list_safe_reset_next is called after re-taking the lock and before
 * completing the current iteration of the loop body.
 */
#define lk_list_safe_reset_next(p_node, n, member)				\
	n = lk_list_next_entry(p_node, member)

/*
 * Double linked lk_lists with a single pointer lk_list head.
 * Mostly useful for hash tables where the two pointer lk_list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */

struct lk_hlist_head {
	struct lk_hlist_node *first;
};

struct lk_hlist_node {
	struct lk_hlist_node *next, **pprev;
};

#define LK_HLIST_POISON1  ((struct lk_hlist_node *) 0x100 + POISON_POINTER_DELTA)
#define LK_HLIST_POISON2  ((struct lk_hlist_node **) 0x200 + POISON_POINTER_DELTA)

#define LK_HLIST_HEAD_INIT { .first = NULL }
#define LK_HLIST_HEAD(name) struct lk_hlist_head name = {  .first = NULL }
#define INIT_LK_HLIST_HEAD(ptr) ((ptr)->first = NULL)

void INIT_LK_HLIST_NODE(struct lk_hlist_node *h);
int lk_hlist_unhashed(const struct lk_hlist_node *h);
int lk_hlist_empty(const struct lk_hlist_head *h);
void lk_hlist_del(struct lk_hlist_node *n);
void lk_hlist_del_init(struct lk_hlist_node *n);
void lk_hlist_add_head(struct lk_hlist_node *n, struct lk_hlist_head *h);
void lk_hlist_add_before(struct lk_hlist_node *n, struct lk_hlist_node *next);
void lk_hlist_add_behind(struct lk_hlist_node *n, struct lk_hlist_node *prev);
void lk_hlist_add_fake(struct lk_hlist_node *n);
int lk_hlist_fake(struct lk_hlist_node *h);
int lk_hlist_is_singular_node(struct lk_hlist_node *n, struct lk_hlist_head *h);
void lk_hlist_move_lk_list(struct lk_hlist_head *old, struct lk_hlist_head *_new);

#define lk_hlist_entry(ptr, type, member) ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

#define lk_hlist_for_each(pos, head) \
	for (pos = (head)->first; pos ; pos = pos->next)

#define lk_hlist_for_each_safe(pos, n, head) \
	for (pos=(head)->first, n=((pos)?((pos)->next):NULL) ; pos ; pos = n, n=((pos)?((pos)->next):NULL) )

#define lk_hlist_entry_safe(ptr, type, member) (ptr==NULL?NULL:lk_hlist_entry(ptr, type, member))

/**
 * lk_hlist_for_each_entry	- iterate over lk_list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_hlist_node within the struct.
 */
#define lk_hlist_for_each_entry(pos, head, type, member)			\
	for (pos = lk_hlist_entry_safe((head)->first, type, member);	\
	     pos;							\
	     pos = lk_hlist_entry_safe((pos)->member.next, type, member))

/**
 * lk_hlist_for_each_entry_continue - iterate over a lk_hlist continuing after current point
 * @pos:	the type * to use as a loop cursor.
 * @member:	the name of the lk_hlist_node within the struct.
 */
#define lk_hlist_for_each_entry_continue(pos, member)			\
	for (pos = lk_hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
	     pos;							\
	     pos = lk_hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

/**
 * lk_hlist_for_each_entry_from - iterate over a lk_hlist continuing from current point
 * @pos:	the type * to use as a loop cursor.
 * @member:	the name of the lk_hlist_node within the struct.
 */
#define lk_hlist_for_each_entry_from(pos, member)				\
	for (; pos;							\
	     pos = lk_hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))

/**
 * lk_hlist_for_each_entry_safe - iterate over lk_list of given type safe against removal of lk_list entry
 * @pos:	the type * to use as a loop cursor.
 * @n:		another &struct lk_hlist_node to use as temporary storage
 * @head:	the head for your lk_list.
 * @member:	the name of the lk_hlist_node within the struct.
 */
#define lk_hlist_for_each_entry_safe(pos, n, head, member) 		\
	for (pos = lk_hlist_entry_safe((head)->first, typeof(*pos), member);\
	     pos && ({ n = pos->member.next; 1; });			\
	     pos = lk_hlist_entry_safe(n, typeof(*pos), member))

#endif
